Binary Heap

Heap

Heap is complete, partially ordered binary tree. Complete means every node at a depth of the tree has subtree that each height differs at most by 1. Partially ordered means that the a element stored in the tree is less than or equal only to its ancestors and greater than or equal only to its descendants, or the other way around.

It is a natural implementation of priority queue which is efficient for the operation that one takes the element with highest priority from the collection.

Heap implementation

In [1]:
import scala.reflect.ClassTag

class BinMaxHeap[T: ClassTag](val heap: Array[T])
                             (implicit val ordering: Ordering[T]) {
  private val maxSize = heap.length
  private var size = maxSize
  buildHeap()

  def heapSize: Int = size

  def isLeaf(pos: Int): Boolean = (pos >= size / 2) && (pos < size)

  def leftChild(pos: Int): Option[Int] = {
    pos match {
      case _ if pos >= size / 2 => None
      case _ => Some(2 * pos + 1)
    }
  }

  def rightChild(pos: Int): Option[Int] = {
    pos match {
      case _ if pos < (size - 1) / 2 => None
      case _ => Some(2 * pos + 2)
    }
  }

  def parent(pos: Int): Option[Int] = {
    pos match {
      case _ if pos <= 0 || pos >= size => None
      case _ => Some((pos - 1) / 2)
    }
  }

  def insert(element: T): Unit = {
    if (size >= maxSize) return
    var curr = size
    size += 1
    heap(curr) = element
    while(curr != 0 && ordering.compare(heap(curr), heap(parent(curr).get)) > 0) {
      val parentCurr = parent(curr).get
      val temp = heap(parentCurr)
      heap(parentCurr) = heap(curr)
      heap(curr) = temp
      curr = parentCurr
    }
  }

  def siftDown(pos: Int): Unit = {
    if (pos < 0 || pos >= size) return
    var curr = pos
    while(!isLeaf(curr)) {
      // if it is not a leaf, then it must have left child
      var left = leftChild(curr).get
      if (left < size - 1 && ordering.compare(heap(left), heap(left + 1)) < 0)
        left += 1
      if (ordering.compare(heap(curr), heap(left)) >= 0) return
      val temp = heap(curr)
      heap(curr) = heap(left)
      heap(left) = temp
      curr = left
    }
  }

  def buildHeap(): Unit = {
    for(i <- (size - 1)/ 2 to 0 by -1) siftDown(i)
  }

  def removeMax(): Option[T] = {
    size match {
      case 0 => None
      case _ =>
        size -= 1
        val maxValue = heap(0)
        heap(0) = heap(size)
        if (size != 0) siftDown(0)
        Some(maxValue)
    }
  }

  def remove(pos: Int): Option[T] = {
    pos match {
      case _ if pos < 0 || pos >= size => None
      case _ =>
        size -= 1
        val value = heap(pos)
        heap(pos) = heap(size)
        var curr = pos
        while (curr > 0 && ordering.compare(heap(curr), heap(parent(curr).get)) > 0) {
          val temp = heap(curr)
          heap(curr) = heap(parent(curr).get)
          heap(parent(curr).get) = temp
          curr = parent(curr).get
        }
        if (size != 0) siftDown(curr)
        Some(value)
    }
  }
}
Out[1]:
import scala.reflect.ClassTag


defined class BinMaxHeap

Analysis of the implementation

The completeness and order must be preserved when an element is inserted and when an element is removed. This means that implementation of inserting and removing elements are not straightforward and need extra opration.

The implementation above realizes them by sift down and sift "up". They move the element smaller than its children down the tree, and bigger up the tree.

Since the heap is always the complete binary tree, those operation takes $\Theta(\log n)$ time in the worst cases. It leads to the fact that inserting and removing an element also take $\Theta(\log n)$ time. For buildHeap, it takes $\Theta(n)$ time (the sum of the series has a closed form).

Using heap as priority queue and for sorting

With methods buildHeap and removeMax, heap can be used for sorting collections and is is called heapsort.

Heap is an implementation of priority queue, however, there are more efficient data structures for it.